1763D - Valid Bitonic Permutations - CodeForces Solution

#include<bits/stdc++.h>
#define ll long long
#define linf 0x3f3f3f3f3f3f3f3f
#define inf 0x7fffffff
#define INF 0x3f
#define v e[i].y
using namespace std;
inline ll read(){
    char ch=getchar();ll x=0,w=1;
    while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
    while(isdigit(ch))x=(x<<1)+(x<<3)+ch-48,ch=getchar();return w==1?x:-x;
}
inline void write(ll x){
    if(x<0)x=-x,putchar('-');
    if(x<10){putchar(48+x);return;}
    write(x/10),putchar((x+10)%10+48);
}
const ll mod=1e9+7;
ll T=read(),n,o1,o2,o3,o4,ans,facinv[1005],fac[1005];
ll qpow(ll x,ll y){
    ll an=1;
    for(;y;y>>=1){
        if(y&1)an=an*x%mod;
        x=x*x%mod;
    }
    return an;
}
ll C(ll x,ll y){
    if(x<y)return 0ll;
    if(x<0||y<0)return 0ll;
    if(y==0)return 1ll;
    return facinv[y]*facinv[x-y]%mod*fac[x]%mod;
}
void solve(){
    n=read(),o1=read(),o2=read(),o3=read(),o4=read(),ans=0;
    if(o3==n){
        if(o1==1){cout<<0<<endl;return;}
        write(C(n-o4-1,o2-o1-1)*C(o4-1,n-o2)%mod),putchar(10);
        return;
    }
    if(o4==n){
        if(o2==n){cout<<0<<endl;return;}
        write(C(n-o3-1,o2-o1-1)*C(o3-1,o1-1)%mod),putchar(10);
        return;
    }
    if(o3>o4)o1=n-o1+1,o2=n-o2+1,swap(o1,o2),swap(o3,o4);//为了只写一遍，就把图形作个对称
    for(int i=o1+1;i<o2;i++)ans=(ans+C(n-o4-1,o2-i-1)*C(o4-o3-1,n-o2-(o3-o1))%mod*C(o3-1,o1-1)%mod)%mod;
    for(int i=o2+1;i<n;i++)ans=(ans+C(n-o4-1,i-o2-1)*C(o4-o3-1,o2-o1-1)%mod*C(o3-1,o1-1)%mod)%mod;
    write(ans),putchar(10);
}
int main(){
    facinv[0]=fac[0]=1;
    for(int i=1;i<=1000;i++)facinv[i]=facinv[i-1]*qpow(i,mod-2)%mod,fac[i]=fac[i-1]*i%mod;
    while(T--)solve();
    return 0;
}